אלגוריתמי מיונים מבוססי השוואות:

• ממיינים על סמך השוואות בין זוגות מפתחות בלבד.
• כל אלגוריתמי ההשוואה הדטרמיניסטים ניתנים למידול באמצעוץ עץ החלטות.
• גובה עץ ההחלטה הוא החסם התחתון של סיבוכיות הזמן של האלגוריתם.
• הסיבוכיות של אלגוריתמים מסוג זה היא: $\mathrm{\Omega }(n\log n)$

אלגוריתמי מיון בזמן ליניארי:

• אלגוריתמים אלו אינם מבוססי השוואות ופועלים בזמן ריצה ליניארי תחת הנחות ספציפיות על הקלט.
• מיון מנייה (Counting Sort):
  • סופר כמה פעמים מופיע כל אחד מהמפתחות ולפי כך יודע איך לסדר את האיברים.
  • מניח שכל ערכי הקלט הם מספרים שלמים הנמצאים בטווח מ-$0$ ועד $k$.
  • זמן הריצה של האלגוריתם הוא $\mathrm{\Theta }(n+k)$. במקרה שבו $k=O(n)$, יורד זמן הריצה ל-$\mathrm{\Theta }(n)$.
  • אלגוריתם מיון מנייה הוא אלגוריתם מיון יציב.
• מיון בסיס (Radix Sort):
  • ממיין מספרים על ידי הפעלת אלגוריתם מיון יציב על כל ספרה בנפרד (בדרך כלל תוך שימוש במיון מנייה), החל מהספרה הימנית ביותר (הספרה הפחות משמעותית).
  • עבור קלט של $n$ מספרים בעלי $d$ ספרות המיוצגים בבסיס $b$, סיבוכיות הזמן תהיה $\mathrm{\Theta }(d(n+b))$.
  • אם הקלט הוא קבוצה של $n$ מספרים שלמים מהתחום $0,1,\dots ,n^c-1$ (כאשר $c$ הוא קבוע), מיון בסיס ירוץ בזמן $\mathrm{\Theta }(n)$.
  • כאשר מנתחים $n$ מספרים המיוצגים בעזרת $t$ ביטים: אם $t\le \log n$ סיבוכיות הזמן היא $\mathrm{\Theta }(n)$, ואם $t>\log n$ הסיבוכיות היא $\mathrm{\Theta }(tn/\log n)$.
• מיון דלי (Bucket Sort):
  • אלגוריתם המיועד למערכים שבהם הערכים הם מספרים המצויים בתחום החצי-פתוח $[0,1)$.
  • האלגוריתם מחלק את הקטע ל-$n$ תתי-קטעים שווים ("דליים"), מפזר את האיברים לדליים המתאימים, ממיין כל דלי בנפרד (לרוב בעזרת מיון הכנסה), ומשרשר את התוצאות לפי הסדר.
  • סיבוכיות זמן הריצה במקרה הממוצע (Average-case) היא $\mathrm{\Theta }(n)$, בהנחה שאיברי המערך נדגמו באקראי ובהתפלגות אחידה ובלתי תלויה מהקטע $[0,1)$.
  • זהו אלגוריתם דטרמיניסטי. זמן הריצה במקרה הממוצע הוא מושג נפרד ושונה מתוחלת זמן הריצה במקרה הגרוע.
  • המקרה הגרוע ביותר של האלגוריתם מתרחש כאשר הקלט גורם לכל האיברים במערך ליפול אל תוך אותו דלי בדיוק.

תכונות נוספות של אלגוריתמי מיון:

• במקום (In place): אלגוריתם שבו רק מספר קבוע של איברי הקלט נשמרים מחוץ למערך במהלך המיון.
• יציב (Stable): אלגוריתם שבו שני ערכים זהים משמרים את סדר הופעתם במערך המקורי גם במערך הממויין .
• זיכרון נוסף (Additional space): כמות הזיכרון (כולל המקום הנדרש עבור מחסנית הקריאות) שהאלגוריתם צורך בנוסף למערך הקלט המקורי.
• לדוגמה, מיון הכנסה דורש זיכרון נוסף של $\mathrm{\Theta }(1)$, מיון מיזוג דורש $\mathrm{\Theta }(n)$, ואילו Quicksort דורש (בתוחלת) $\mathrm{\Theta }(\log n)$.